/*Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?
*/

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> cur(1,1), next;
        if (!rowIndex) return cur;
        for (int i = 2; i <= rowIndex+1; i++) {
            int len = cur.size();
            next.push_back(cur[0]);
            for (int k = 0; k < len-1; k++) {
                next.push_back(cur[k] + cur[k+1]);
            }
            next.push_back(cur[len-1]);
            swap(cur, next); next.clear();
        }
        return cur;  
    }
};
